package com.lsa.letcode.the128.longestConseq;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int longestConsecutive(int[] nums) {
    	if (nums == null || nums.length == 0){
    		return 0;
    	}
		return doLongestConsecutive(nums).length();
    }
    
    Run doLongestConsecutive(int[] nums) {
    	Map<Integer, Run> from2Run = new HashMap<Integer, Run>();
    	Map<Integer, Run> to2Run = new HashMap<Integer, Run>();
    	
		int maxLength = 0;
		Run maxRun = null;
    	for (int i : nums) {
    		Run newRun = new Run(i);
    		boolean isStop;
    		do{
				Run newRun2 = union(from2Run.remove(newRun.from),
						from2Run.remove(newRun.to), to2Run.remove(newRun.from),
						to2Run.remove(newRun.to), newRun);
        		isStop = newRun2.equals(newRun);
        		if (isStop){
        			from2Run.put(newRun.from, newRun);
        			to2Run.put(newRun.to, newRun);
        		}
        		else {
        			newRun = newRun2;
        		}
    		}
    		while(!isStop);
    		int newMaxLength = newRun.length();
    		if (newMaxLength > maxLength){
    			maxRun = newRun;
    			maxLength = newMaxLength;
    		}
		}
    	return maxRun;
    }
    
    static Run union(Run r1, Run r2){
    	if (r1 == null){
    		return r2;
    	}
    	else if (r2 == null){
    		return r1;
    	}
		return new Run(Math.min(r1.from, r2.from), Math.max(r1.to, r2.to));
	}
    
    static Run union(Run... runs){
    	if (runs.length == 0){
    		return null;
    	}
    	Run res = runs[0];
    	for (int i = 1; i < runs.length; i++) {
    		res = union(res, runs[i]);
		}
    	return res;
    }
    
    /**
     * (from, to]
     */
    static class Run {
    	int from;
    	int to;
    	
    	Run(int from, int to) {
			this.from = from;
			this.to = to;
		}
    	
    	Run(int n){
    		this.from = n - 1;
    		this.to = n;
    	}

		int length(){
			return this.to - this.from;
		}
		
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + from;
			result = prime * result + to;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			Run other = (Run) obj;
			if (from != other.from)
				return false;
			if (to != other.to)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return String.format("[%s,%s]", from + 1, to);
		}
    }
}